package algorithm.dynamicProgramming.p343;

import java.util.Arrays;

/**
 * @Author CandyWall
 * @Date 2022/2/21--0:09
 * @Description
 */
public class Solution {
    private int[] memo;
    public int integerBreak(int n) {
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return breakInteger(n);
    }

    private int breakInteger(int n) {

        if(n == 1) return 1;

        if(memo[n] != -1) return memo[n];

        int res = -1;
        for(int i = 1; i < n; i++) {
            res = Math.max(res, i * (n - i));
            res = Math.max(res, i * breakInteger(n - i));
        }

        memo[n] = res;

        return res;
    }
    public static void main(String[] args) {
        System.out.println(new Solution().integerBreak(2));
    }
}
